#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 13:39
# @USER    : Shengji He
# @File    : SpiralMatrix.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """
        Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

        Example 1:

        Input:
            [
             [ 1, 2, 3 ],

             [ 4, 5, 6 ],

             [ 7, 8, 9 ]
            ]
        Output: [1,2,3,6,9,8,7,4,5]

        Example 2:

        Input:
            [
              [1, 2, 3, 4],

              [5, 6, 7, 8],

              [9,10,11,12]
            ]

        Output: [1,2,3,4,8,12,11,10,9,5,6,7]

        :param matrix: List[List[int]]
        :return: List[int]
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []
        m, n = len(matrix) - 1, len(matrix[0]) - 1
        ms, ns = 0, 0
        ans = []
        while ms <= m and ns <= n:
            if ms == m and ns == n:
                ans.append(matrix[ms][ns])
                return ans
            elif ns < n and ms == m:
                for j in range(ns, n + 1, 1):
                    ans.append(matrix[ms][j])
            elif ns == n and ms < m:
                for i in range(ms, m + 1):
                    ans.append(matrix[i][n])
            else:
                for j in range(ns, n, 1):
                    ans.append(matrix[ms][j])
                for i in range(ms, m):
                    ans.append(matrix[i][n])
                for j in range(n, ns, -1):
                    ans.append(matrix[m][j])
                for i in range(m, ms, -1):
                    ans.append(matrix[i][ns])
            ms += 1
            ns += 1
            n -= 1
            m -= 1
        return ans


if __name__ == '__main__':
    S = Solution()
    # matrix = [[6, 9, 7]]
    # matrix = [[6], [9], [7]]
    # matrix = [[]]
    # matrix = [[1, 2, 3], [5, 6, 7,], [9, 10, 11,], [12, 13, 14]]
    # matrix = [[1, 2, ], [4, 5,]]
    matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    print(S.spiralOrder(matrix))
    print('done')
